In many applications such as the field of networking, it is highly desirable to maintain a list of items that are ordered in some type of fashion, i.e., alphabetical, numerical, chronological, etc. The list comprises a form of a database wherein small or large amounts of data can be maintained in the ordered list. The fact that the list is maintained as an ordered list enables easy and relatively fast access to large databases of items. For example, many networking device applications need to keep track and store MAC addresses for various reasons such as network bridge applications.
One conventional solution to the problem stores the ordered list in regular memory. A diagram illustrating a prior art example of a block of memory utilized to store and maintain an ordered list of data is shown in FIG. 1. The block of memory 10 comprises a plurality of memory locations 12 numbered 1 through N. Each memory location holds one item of data Data items can be inserted and deleted from the list using push and pop operations. Assuming data is to be inserted at the index point, a push operation functions to move all locations below the index down one space and inserts the new data into the location at the index point. Removing an item from the index location involves reading the location at the index point and then moving all locations below the index up one space.
Note that this prior art scheme can be performed using either software or hardware means. In the case of software, the push and pop operations are time consuming and could take relatively long periods of time to complete as the size of the list increases. Handling large lists in hardware require large number of components to construct the necessary circuitry to perform the push and pop operations.
A second prior art solution to the problem uses a singly or doubly linked list to maintain the ordered list. In a pointer linked list implementation, each data item is combined with one or more pointer fields in which each pointer field functions to store one pointer. In the case of a doubly linked list, two pointers are stored to keep track of both the next data item in the list and the previous data item in the, list. The next and previous pointers are chosen such that they maintain the order in the list.
A diagram illustrating another prior art example of a portion of a doubly linked list utilized to store and maintain an ordered list of data is shown in FIG. 2. The linked list, generally referenced 20, comprises a plurality of structures 22 wherein each structure represents one index. For illustrative purposes, only index #X, #Y and #Z are shown. Each structure 22 comprises a list cell 24 which contains the data to be stored in the list, a next pointer 26 and a previous pointer 28. As shown by the arrows, the next and previous pointers dictate the order of the indexes in the list. For example, the next pointer of index #X points to index #Y and the previous pointer of index Z points to index #Y.
If an item is to be added to the list, the appropriate place of insertion is determined by some process that functions to maintain the ordering scheme. To add an item, the linked list is broken at an appropriate place and the new item placed therein. The linked list is then closed. A diagram illustrating the prior art example shown in FIG. 2 after the insertion of a new index entry is shown in FIG. 3.
The new linked list, generally referenced 30, now comprises a new item--index #M. The ordering mechanism has determined that item #M is to be inserted between index #Y and index #Z. To insert item #M, the next pointer of index #Y is modified to point to index #M and the previous pointer of index #Z is set to point to index #M. Similarly, the next pointer of index #M is set to point to index #Z and the previous pointer of index #M is set to point to index #Y.
A disadvantage of using linked lists, created using either hardware or software, is that locating and reading out a particular entry can be time consuming. In addition, the insert and remove operations can be time consuming as well, especially as the number of entries grows larger and larger. This is due to the fact that to find an entry, the linked list must be traversed link by link. There is no quick random access technique that permits quick reading of any arbitrary data item.
Other prior art schemes of maintaining an ordered list typically implement a hashing scheme or involve some form of content addressable memory (CAM) technique. These techniques also have the disadvantage of requiring relatively large amounts of software and/or hardware resources.